package backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : Rookie
 * @description :和为n 全部组合 每个数只能被选择一次
 * @date : 2023/11/25
 */
public class AssemblySum3 {

    public static void main(String[] args) {
        int[] candidates = new int[] {10,1,2,7,6,1,5};
        int target = 8;

        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates,target,0,new ArrayList<>(),result);
        System.out.println(result);
    }

    private static void backtrack(int[] candidates, int target, int startIndex, List<Integer> path,List<List<Integer>> result)  {
        Integer sum = path.stream().reduce(Integer::sum).orElse(0);
        if (sum.equals(target)) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            // 防止重复选择
            if (i>startIndex && candidates[i] == candidates[i-1]) {
                continue;
            }
            path.add(candidates[i]);
            backtrack(candidates, target, i+1, path, result);
            path.remove(path.size()-1);
        }
    }
}
